//
//  main.c
//  002--括号匹配检验
//
//  Created by Shawn Li on 2020/5/12.
//  Copyright © 2020 Shawn. All rights reserved.
//

#include <stdio.h>
#include <string.h>
#include "stdlib.h"
#include "math.h"
#include "time.h"

//题目：假设字符串中仅包含两种括号：圆括号与方括号，其中的嵌套顺序随意，即 ([]()) 或者 [([][])] 都是正确的，而 [(] 或者 ([()) 都不是正确的格式。设计算法检验括号是否匹配可用。
//本题使用链式更好，可以根据输出自行动态适配空间，不过思想不变，此处只为演示。

#define SUCCESS 1
#define ERROR 0

#define TRUE 1
#define FALSE 0

//存储空间初始分配量
#define MAXSIZE 500

//需要转换到的进制
#define SYSTEMNUM 8


typedef int Status;

typedef char ItemType;


typedef struct {
    ItemType data[MAXSIZE];
//    栈顶
    int top;
} ListStack;

//构建空栈
Status stackInit(ListStack *s){
    s->top = -1;
    return SUCCESS;
}

//清空堆栈
Status stackClear(ListStack *s){
    s->top = -1;
    return SUCCESS;
}

//判空
Status isStackEmpty(ListStack s){
    return s.top == -1 ? TRUE : FALSE;
}

//获得堆栈的长度
int stackLength(ListStack s){
    return s.top + 1;
}

//获取栈顶元素
Status stackGetTop(ListStack s, ItemType *e){
    if (isStackEmpty(s)) {
        return ERROR;
    }
    *e = s.data[s.top];
    return SUCCESS;
}

//压栈
Status stackPush(ListStack *s, ItemType e){
    if (s->top == MAXSIZE - 1) {
        return ERROR;
    }
    
    s->top++;
    s->data[s->top] = e;
    
    return SUCCESS;
}

//弹栈
Status stackPop(ListStack *s, ItemType *e){
    if (isStackEmpty(*s)) {
        return ERROR;
    }
    
    *e = s->data[s->top];
    s->top--;
    
    return SUCCESS;
}


/// 输出一下栈
/// @param s 堆栈
Status stackPrint(ListStack s){
    printf("堆栈信息\n");
    for (int i = 0; i <= s.top; i++) {
        printf("%c ", s.data[i]);
    }
    printf("\n");
    return SUCCESS;
}

//思路：
//1.首字符入栈。
//2.查看栈顶，如果栈顶是 （ 恰好当前元素就是 ），那么栈顶出栈（这一组就匹配好了，不用管了）。如果不是，那么入栈当前元素（他需要别人和它匹配）。
//3.使用相同的逻辑判断 [
//4.多组判断中，以 # 间隔，那么一定要以 ( 或 [ 开始，否则即为不合法字符串。
//5.最后遍历处理完毕之后若栈中没有待匹配的字符，那么即为合法。

int execute(ListStack stack, char* str){
    stackPush(&stack, str[0]);
    
    ItemType e;
    
    for (int i = 1; i < strlen(str); i++) {
        char top;
        stackGetTop(stack, &top);
        stackPrint(stack);
        switch (top) {
            case '(':
                if (str[i] == ')') {
                    stackPop(&stack, &e);
                } else {
                    stackPush(&stack, str[i]);
                }
                break;
            case '[':
                if (str[i] == ']') {
                    stackPop(&stack, &e);
                } else {
                    stackPush(&stack, str[i]);
                }
                break;
            case '#':
                if (str[i] == '(' || str[i] == '[') {
                    stackPush(&stack, str[i]);
                }
                break;
                
            default:
                return -1;
                break;
        }
    }
    
    if (isStackEmpty(stack)) {
        return 0;
    }
    
    return -1;
}


int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World!\n");
    
    ListStack s;
    stackInit(&s);
    char input[MAXSIZE];
    printf("请输入括号字符串：\n");
    scanf("%s", input);
    
    printf(execute(s, input) == -1 ? "括号匹配失败！\n" : "括号匹配成功！\n");
    
    return 0;
}

